package leetcode.d_300_plus;

public class P416 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int i=0; i<n; i++) {
            sum += nums[i];
        }
        if (sum%2 != 0) {
            return false; // 和是奇数则无法分割为等和子集
        }
        int target = sum / 2;

        // 定义状态方程: 背包问题
        // dp 数组的定义：dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时
        // 若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满
        boolean[][] dp = new boolean[n+1][target+1];
        for (int i=1; i<=n; i++) {
            dp[i][0] = true;
        }
        // 如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，
        //取决于上一个状态 dp[i-1][j]，继承之前的结果。

        //如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，
        // 取决于状态 dp[i-1][j-nums[i-1]]。
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=target; j++) {
                if (j - nums[i-1] < 0) {
                    // 背包容量不足，不能装入第i个物品
                    dp[i][j] = dp[i-1][j];
                }else {
                    // 装入或不装入背包
                    dp[i][j] =  dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }
}
